蛮三刀酱的博客

技术公众号:后端技术漫谈

【Leetcode】【python】Permutations 全排列

发表于 更新于 分类于 阅读次数： Valine：

题目大意

求一组数的全排列

解题思路

回溯，想起来思路很简单，实际写的时候遇到了很多麻烦。

代码

递归

可能更容易理解，但是代码复杂度高

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution(object):
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        self.res = []
        sub = []
        self.dfs(nums,sub)
        return self.res

    def dfs(self, Nums, subList):
        if len(subList) == len(Nums):
            #print res,subList
            self.res.append(subList[:])
        for m in Nums:
            if m in subList:
                continue
            subList.append(m)
            self.dfs(Nums,subList)
            subList.remove(m)

递归方法二

例子：ABC

1
2
3
4
5
n = nums[:i] + nums[i+1:]
n = BC
n = A + C = AC
n = AB
最后在ABC+（BC+C）+（AC+A）+（AB+B）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution(object):
    

    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        print 'nums', nums
        if len(nums) <= 1: 
            return [nums]
        ans = []
        for i, num in enumerate(nums):
            n = nums[:i] + nums[i+1:]  # n是剩余数的list
            print nums[:i], '+', nums[i+1:], '=', n
            for y in self.permute(n):  # 直到函数有return，一个数的时候[nums]，所以y是list
                print '递归内：'
                print [num], '+', y, '=',[num] + y
                ans.append([num] + y)
            print '-----End-----'
        return ans

输出：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
nums [1, 2, 3]
[] + [2, 3] = [2, 3]
nums [2, 3]
[] + [3] = [3]
nums [3]
递归内：
[2] + [3] = [2, 3]
-----End-----
[2] + [] = [2]
nums [2]
递归内：
[3] + [2] = [3, 2]
-----End-----
递归内：
[1] + [2, 3] = [1, 2, 3]
递归内：
[1] + [3, 2] = [1, 3, 2]
-----End-----
[1] + [3] = [1, 3]
nums [1, 3]
[] + [3] = [3]
nums [3]
递归内：
[1] + [3] = [1, 3]
-----End-----
[1] + [] = [1]
nums [1]
递归内：
[3] + [1] = [3, 1]
-----End-----
递归内：
[2] + [1, 3] = [2, 1, 3]
递归内：
[2] + [3, 1] = [2, 3, 1]
-----End-----
[1, 2] + [] = [1, 2]
nums [1, 2]
[] + [2] = [2]
nums [2]
递归内：
[1] + [2] = [1, 2]
-----End-----
[1] + [] = [1]
nums [1]
递归内：
[2] + [1] = [2, 1]
-----End-----
递归内：
[3] + [1, 2] = [3, 1, 2]
递归内：
[3] + [2, 1] = [3, 2, 1]
-----End-----

答案：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

清爽版：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        print 'nums', nums
        if len(nums) <= 1: 
            return [nums]
        ans = []
        for i, num in enumerate(nums):
            n = nums[:i] + nums[i+1:]
            for temp_list in self.permute(n):
                ans.append([num] + temp_list)
            print '-----End-----'
        return ans

总结